/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;

    struct ListNode* tail = NULL;
    struct ListNode* head = NULL;

    while(list1 && list2){
        if(list1->val < list2->val){
            if(tail == NULL)
                tail = head = list1;
            else{
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }else{
            if(tail == NULL)
                tail = head = list2;
            else{
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if(list1){
        tail->next = list1;
    }
    if(list2){
        tail->next = list2;
    }

    return head;
}

//优化
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;

    struct ListNode* tail = NULL;
    struct ListNode* head = NULL;

    if(list1->val < list2->val){
        tail = head = list1;
        list1 = list1->next;
    }else{
        tail = head = list2;
        list1 = list1->next;

    }
    while(list1 && list2){
        if(list1->val < list2->val){
            tail->next = list1;
            list1 = list1->next;
        }else{
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    if(list1){
        tail->next = list1;
    }
    if(list2){
        tail->next = list2;
    }

    return head;
}

/*将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。*/